package com.ls.day9;

import java.util.ArrayList;
import java.util.Arrays;
import java.util.List;

public class FourSum {

    public static void main(String[] args) {
        List<List<Integer>> result = fourSum(new int[]{-1,-5,-5,-3,2,5,0,4},-7);
        for (List<Integer> items:result){
            for (Integer item:items){
                System.out.print(item+" ");
            }
            System.out.println("");
        }
    }

    public static List<List<Integer>> fourSum(int[] nums, int target) {
        List<List<Integer>> result = new ArrayList<>();
        if (nums.length<4) return result;
        Arrays.sort(nums);

        for(int i=0;i<nums.length;i++){
            int L1=i+1,L2,R=nums.length-1;
            if (i>0 &&  nums[i]==nums[i-1]) continue;
            while (L1<R){
                L2=L1+1;
                R=nums.length-1;
                while (L2<R){
                    int tmp = nums[i]+nums[L1]+nums[L2]+nums[R];
                    if (tmp==target){
                        List<Integer> t = new ArrayList<>();
                        t.add(nums[i]);
                        t.add(nums[L1]);
                        t.add(nums[L2]);
                        t.add(nums[R]);
                        result.add(t);
                        while (L2<R && nums[L2]==nums[L2+1])L2++;
                        while (L2<R && nums[R]==nums[R-1])R--;
                        L2++;
                        R--;
                    }else if (tmp<target){
                        L2++;
                    }else R--;
                }
                while (L1<R && nums[L1]==nums[L1+1])L1++;
                L1++;
            }
        }
        return result;
    }
}
